// 113.路径总和2
package Leetcode_Second_Brush;

import java.util.ArrayList;
import java.util.List;

public class Solution113 {
    private final List<List<Integer>> result = new ArrayList<>();

    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        findPaths(root, targetSum, new ArrayList<>());
        return result;
    }

    private void findPaths(TreeNode node, int remainingSum, List<Integer> path) {
        if (node == null)
            return;

        path.add(node.val);

        // 如果当前是叶子节点且值相等，则保存路径
        if (node.left == null && node.right == null && node.val == remainingSum) {
            result.add(new ArrayList<>(path));
        }
        // 否则递归寻找左右子树的路径
        else {
            findPaths(node.left, remainingSum - node.val, path);
            findPaths(node.right, remainingSum - node.val, path);
        }

        path.remove(path.size() - 1); // Backtrack to explore other paths
    }
}
